package likou.tanxin;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author: Tangxz
 * @email: 1171702529@qq.com
 * @cate: 2020/11/21 08:21
 */

/**
 * 返回true和false的方法，不用必须按照题目要求进行操作，可以用可替代的逻辑来进行判断。
 */
public class _1094 {
    public static void main(String[] args) {
        System.out.println(carPooling(new int[][]{{3, 2, 7}, {3, 7, 9}, {8, 3, 9}}, 11));
    }

    public static boolean carPooling(int[][] trips, int capacity) {
        //根据起始点排队
        quickSort(trips,0,trips.length-1);
        //PriorityQueue存储的是当前已上车的波数
        //int[]，只存两位，第一位为人数，第二位为下车点，根据下车点顺序排序。
        PriorityQueue<int[]> queue = new PriorityQueue<>(Comparator.comparingInt(i1 -> i1[1]));
        for (int i = 0; i < trips.length; i++) {
            //能塞就塞。
            if (trips[i][0] <= capacity) {
                capacity -= trips[i][0];
                queue.add(new int[]{trips[i][0], trips[i][2]});
                continue;
            }
            //留下当前上车点
            int nowShang = trips[i][1];
            //不能塞就去堆里面看，是否还可以把人踢走。
            if (queue.size() > 0 && nowShang >= queue.peek()[1]) {
                //堆不为空，且下车点小于等于上车点
                while (queue.size() > 0 && nowShang >= queue.peek()[1]) {
                    int[] nowXia = queue.poll();
                    capacity += nowXia[0];
                }
                i--;
            } else {
                return false;
            }
        }
        return true;
    }

    public static void quickSort(int[][] trips, int startIndex, int endIndex) {
        if (startIndex >= endIndex) {
            return;
        }
        int pivot = partition(trips, startIndex, endIndex);
        quickSort(trips, startIndex, pivot - 1);
        quickSort(trips, pivot + 1, endIndex);
    }

    public static int partition(int[][] trips, int startIndex, int endIndex) {
        int left = startIndex, right = endIndex;
        int[] pivot = trips[startIndex];
        while (left != right) {
            while (left < right && trips[right][1] > pivot[1]) {
                right--;
            }
            while (left < right && trips[left][1] <= pivot[1]) {
                left++;
            }
            int[] tem = trips[left];
            trips[left] = trips[right];
            trips[right] = tem;
        }
        trips[startIndex] = trips[left];
        trips[left] = pivot;
        return left;
    }




    public boolean carPooling2(int[][] trips, int capacity) {
        int[] tempNew = new int[1001];
        for (int i = 0; i < trips.length; i++) {
            int num = trips[i][0];
            int start = trips[i][1];
            int end = trips[i][2];
            tempNew[start] = tempNew[start] + num;
            tempNew[end] = tempNew[end] - num;
        }
        int sum = 0;
        for (int i = 0; i < tempNew.length; i++) {
            sum = sum + tempNew[i];
            if (sum > capacity) {
                return false;
            }
        }
        return true;
    }
}
